CSCI 271                        Thacker

Title: Sparse Array

Description: In many mathematical and engineering applications, a huge array is used, but many (well over half) of the entries are 0.  Rather than declare an array of the huge size, you will create a data structure where only the number of non-zero items have allocated space.  For this project, we will store the items in a Binary Sort Tree.

Details:  You will create a class that uses a Binary Sort Tree to hold the non-zero items in a sparse array.  As well as the value, the index/subscript needs to be stored.  For efficiency reasons, the items should be stored in subscript order.

Methods:

• constructor - sets up and initializes the data structure
• copy constructor - makes a copy of the data structure (cannot just copy the head pointer)
• store - is passed the subscript and the value.  If no node with that subscript entry exists, then create a new node and insert.  Otherwise, just change the value in the node.  However, if the value 0 is stored, then no node will be created.  But, if a node already exists for that subscript, then storing a 0 should cause the node to be deleted.
• value - is passed the subscript and returns the value of the data in the node that has the passed subscript.  If no node exists with that subscript, return 0.
• Print-all - this type of method is usually included for debugging purposes.  When invoked, this method will perform an in-order traversal of the Binary Sort Tree, printing out the subscript and data values in the node.

Main: Your main will read in a sparse array of data (defined as subscript value pair of values), store them into the sparse array, then print out the sum of the first 1,000 elements of the array, many of which may be 0. There may be more or less than 1,000 items in the sparse array (not the first 1000 items in the tree) and the largest subscript may be larger or smaller than 1,000.  Then at the end, invoke your Print-All method to show what is in your tree.